package demo;

/**
 * @Author liangzai
 * @Description:
 */
public class Test {
    public boolean isPail (ListNode head) {
        // write code here
        ListNode fast = head;
        ListNode slow = head;
        while(fast!=null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }

        ListNode pcur = slow.next;
        while(pcur!=null){
            ListNode pcurn = pcur.next;
            pcur.next = slow;
            slow = pcur;
            pcur = pcurn;
        }

        while(head!=slow){
            if(head.val!=slow.val){
                return false;
            }
            if(head.next == slow){
                return true;
            }
            head = head.next;
            slow = slow.next;

        }
        return true;
    }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pl = headA;
        ListNode ps = headB;
        int lena=0;
        int lenb=0;
        while(pl!=null){
            pl = pl.next;
            lena++;
        }
        while(ps!=null){
            ps = ps.next;
            lenb++;
        }

        pl = headA;
        ps = headB;
        int len = lena-lenb;
        if((lena - lenb)<0){
            pl = headB;
            ps = headA;
            len = lenb - lena;
        }
        while(len!=0){
            pl = pl.next;
            len--;
        }

        while(pl != ps){
            pl = pl.next;
            ps = ps.next;
        }
        if(pl == null){
            return null;
        }
        return pl;
    }

    public boolean hasCycle(ListNode head) {
        if(head==null){
            return false;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast !=null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                return true;
            }
        }
        return false;
    }

    public ListNode detectCycle(ListNode head) {
        if(head==null){
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast !=null && fast.next!=null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                break;
            }
        }
        if(fast ==null || fast.next==null){
            return null;
        }
        slow = head;
        while(slow != fast){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}
